//
// Created by Yandel on 2024/12/2.
//
/**
 * 层序遍历  使用队列方式
 */
#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    int value;
    struct TreeNode *left, *right;
} TreeNode;

// 队列节点结构体
typedef struct QueueNode {
    TreeNode *treeNode;
    struct QueueNode *next;
} QueueNode;

// 队列结构体
typedef struct Queue {
    QueueNode *front, *rear;
} Queue;

// 创建一个新的二叉树节点
TreeNode* createTreeNode(int value) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->value = value;
    node->left = node->right = NULL;
    return node;
}

// 初始化队列
void initQueue(Queue *queue) {
    queue->front = queue->rear = NULL;
}

// 判断队列是否为空
int isEmptyQueue(Queue *queue) {
    return queue->front == NULL;
}

// 向队列添加元素
void enqueue(Queue *queue, TreeNode *node) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    newNode->treeNode = node;
    newNode->next = NULL;
    if (isEmptyQueue(queue)) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 从队列中移除元素
TreeNode* dequeue(Queue *queue) {
    if (isEmptyQueue(queue)) return NULL;
    QueueNode *temp = queue->front;
    TreeNode *node = temp->treeNode;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return node;
}

// 层序遍历二叉树
void levelOrderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    Queue queue;
    initQueue(&queue);

    // 将根节点入队
    enqueue(&queue, root);

    while (!isEmptyQueue(&queue)) {
        // 从队列中取出节点
        TreeNode *currentNode = dequeue(&queue);
        // 打印当前节点的值
        printf("%d ", currentNode->value);

        // 如果当前节点有左子节点，入队
        if (currentNode->left != NULL) {
            enqueue(&queue, currentNode->left);
        }

        // 如果当前节点有右子节点，入队
        if (currentNode->right != NULL) {
            enqueue(&queue, currentNode->right);
        }
    }
}

int main() {
    // 创建二叉树
    TreeNode *root = createTreeNode(1);
    root->left = createTreeNode(2);
    root->right = createTreeNode(3);
    root->left->left = createTreeNode(4);
    root->left->right = createTreeNode(5);
    root->right->left = createTreeNode(6);
    root->right->right = createTreeNode(7);

    // 层序遍历
    printf("层序遍历结果: ");
    levelOrderTraversal(root);
    printf("\n");

    return 0;
}
